package com.cuz.daileetcode.bat100;

import com.cuz.daileetcode.utils.TreeNode;

public class 相等子树数量 {

    public static int sameTreeOf(TreeNode node) {
        if (node == null) {
            return 0;
        }
        boolean curTreeEqual = equalOf(node.left, node.right);
        return (curTreeEqual ? 1 : 0)
                + sameTreeOf(node.right)
                + sameTreeOf(node.left);
    }

    private static boolean equalOf(TreeNode t1, TreeNode t2) {
        //同时是空 那么是相同子树
        if (t1 == null && t2 == null) {
            return true;
        }
        //存在一个为null 一个不为null 那么必然不是相同子树
        if (t1 == null || t2 == null) {
            return false;
        }
        //都不为空 但是值不同 那么false
        if (t1.val != t2.val) {
            return false;
        }
        //根节点值相同 且t1左树等于t2左树 有树也相等才是相同树
        return equalOf(t1.left, t1.left) && equalOf(t2.right, t1.right);
    }
}
